#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>

#define INIT_LENGTH 20	//数字位数的起始大小

char * inputBigNum(void);	//接收标准输入的数字 存入内存后返回地址 返回的地址需要free
char * bigNumAdd(const char *num1, const char *num2);	//计算num1+num2 结果是一个指针 用完后需要free

int main(void)
{
	char *num1;	//数字1指针
	char *num2;	//数字2指针
	char *res;	//存放结果的指针
	int i;

	printf("Input the first num:\n");
	num1 = inputBigNum();
	while (num1 == NULL)	//判断非法数字
	{
		printf("Invalid num, please input again:\n");
		num1 = inputBigNum();
	}

	printf("Input the second num:\n");
	while ((num2 = inputBigNum()) == NULL)	//判断非法数字
	{
		printf("Invalid num, please input again:\n");
		num2 = inputBigNum();
	}

	res = bigNumAdd(num1, num2);	//计算

	printf("num1: %s\n", num1);
	printf("num2: %s\n", num2);
	printf("res: %s\n", res);

	free(num1);
	free(num2);
	free(res);

	return 0;
}

/*
 * 根据输入数字个数分配内存（采用翻倍增加空间的方式 有效利用率大于50%）
 * 如果输入中有非数字 返回NULL
 * 如果输入是合法数字 返回一个存放该数字字符串的指针 
 * 返回有效指针时，记得用完后释放内存
*/
char * inputBigNum(void)
{
	char *p;
	int i = 0;
	int current_capacity = INIT_LENGTH;
	char ch;
	int ok = 1;

	if ((p = (char *)malloc(INIT_LENGTH * sizeof(char))) == NULL)
		exit(-1);

	while ((ch = getchar()) != '\n')
	{
		p[i++] = ch;
		if (ch < '0' || ch > '9')
		{
			ok = 0;
		}
		//已经写入了i个数字
		if (i+1 == current_capacity)
		{
			if ((p = (char *)realloc(p, current_capacity * 2 * sizeof(char))) == NULL)
				exit(-1);
			current_capacity *= 2;
		}
	}
	p[i] = '\0';

	if (ok == 0)
	{
		free(p);
		return NULL;
	}
	else
	{
		return p;
	}
}

/*
 * 计算num1 + num2 结果是字符串形式 
 * 返回存放结果的字符串地址，记得用完后free
*/
char * bigNumAdd(const char *num1, const char *num2)
{
	int i;

	int num1_len;	//num1的数字位数
	int num2_len;	//num2的数字位数
	int res_len;	//计算结果的数字位数 包括最后的空字符'\0'

	char *n1;	//临时存放num1
	char *n2;	//临时存放num2
	char *res;	//存放结果

	int c = 0;	//每一位上的进位 个位上的进位初始时是0

	//计算长度
	num1_len = strlen(num1);
	num2_len = strlen(num2);
	res_len = num1_len > num2_len ? num1_len : num2_len;

	//分配内存 两个加数最高位的更高一位设置为0 结果包含可能的进位和空字符'\0'
	if ((n1 = (char *)malloc(res_len * sizeof(char) + 1)) == NULL)
		exit(-1);
	if ((n2 = (char *)malloc(res_len * sizeof(char) + 1)) == NULL)
		exit(-1);
	if ((res = (char *)malloc(res_len * sizeof(char) + 2)) == NULL)
		exit(-1);
	memset(n1, 0, res_len * sizeof(char) + 1);
	memset(n2, 0, res_len * sizeof(char) + 1);
	memset(res, 0, res_len * sizeof(char) + 2);
	
	//将原加数按照逆序存入n1和n2 同时转换为数字
	for (i = 0; i < num1_len; ++i)
	{
		n1[i] = num1[num1_len-i-1] - '0';
	}
	for (i = 0; i < num2_len; ++i)
	{
		n2[i] = num2[num2_len-i-1] - '0';
	}

	//按位进行加运算
	for (i = 0; i < res_len + 1; ++i)
	{
		res[res_len-i] = ((n1[i] + n2[i] + c) % 10) + '0';	//结果最高位是个位
		c = (n1[i] + n2[i] + c) / 10;	//进位
	}
	res[res_len+1] = '\0';	//设置末尾的空字符

	//释放临时内存
	free(n1);
	free(n2);

	return res;
}